package recursion

import problem.Problem

class Q779KthSymbolInGrammar extends Problem {

  def kthGrammar(N: Int, K: Int): Int = {
    if (N == 1 || K == 1) 0
    else kth(N - 1, (K + 1) / 2, K % 2 == 1)
  }

  def kth(n: Int, k: Int, left: Boolean): Int = {
    if (n == 1) {
      if (left) 0 else 1
    } else {
      val v = kth(n - 1, (k + 1) / 2, k % 2 == 1)
      if (v == 0 && left || v == 1 && !left) 0
      else 1
    }
  }

  override def test(): Unit = {
    kthGrammar(1, 1) shouldBe 0
    kthGrammar(2, 1) shouldBe 0
    kthGrammar(2, 2) shouldBe 1
    kthGrammar(4, 5) shouldBe 1
    kthGrammar(3, 2) shouldBe 1
  }
}
